package DataStructure.arrayAndList.list.listReverse;

import DataStructure.arrayAndList.list.Nodelj;
import Top100.Reversal;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/12/7
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 链表反转
 * 反转从index1 到 index2 之间的数据，区间是 左闭右闭
 */

public class ListReverseTwoPosition implements Reversal {

    public Nodelj reverse(Nodelj node1, Nodelj node2) {
        if (node1 == null || node1 == node2) {
            return node1;
        }
        Nodelj head = node1;
        Nodelj pre = null;
        Nodelj newNode = null;

        while (node1 != node2) {
            pre = node1;
            node1 = node1.next;
            pre.next = newNode;
            newNode = pre;
        }
        node2.next = newNode;
        return node2;
    }

    // tips:注意是原址，所以测试用例不可复用
    public Nodelj reverse(Nodelj head, int index1, int index2) {
        if (head == null || index1 >= index2) {
            return head;
        }
        if (index1 <= 0) {
            index1 = 1;
        }

        int curIndex = 1;
        Nodelj cur = head;
        Nodelj partOneTail = null;

        while (cur != null && curIndex < index1) {
            partOneTail = cur;
            cur = cur.next;
            curIndex++;
        }
        // 不满足起始地址
        if (cur == null || curIndex != index1) {
            return head;
        }

        Nodelj partTwoTail = cur;
        Nodelj partTwoHead = partTwoTail;
        Nodelj pre = null;
        while (cur != null && curIndex <= index2) {
            // 进行指针反转
            pre = cur;
            cur = cur.next;
            pre.next = partTwoHead;
            partTwoHead = pre;
            curIndex++;
        }
        // 整理两部分的链接

        partTwoTail.next = cur;
        if (partOneTail != null) {
            partOneTail.next = partTwoHead;
            return head;
        }
        return partTwoHead;
    }
}
